/********************************************************/
/* Aluno: Luciano G. S. Ramalho                         */
/* Numero USP: 1002101                                  */
/* Exercicio-Programa 1 -- Maquina Vendedora Automatica */
/* MAC110 (BCC) -- 2007 -- Professor: Reverbel          */
/* Compilador: gcc (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5)  */
/********************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define QT_VAL_DISTINTOS (sizeof(VAL_NUMERARIO) / sizeof(VAL_NUMERARIO[0]))

#define SEM_TROCO -1

const int VAL_NUMERARIO[] = {1000, 500, 200, 100, 50, 25, 10, 5};

int lerInts(int qtd_ler, int vetor[]);
void exibirCabecalho();
void exibirNumerario(int numer[]);
void zerarNumerario(int numer[]);
void retirarNumerario(int caixa[], int troco[]);
int totalizarNumerario(int numer[]);
int trocar(int total);
int fazerTroco(const int total, const unsigned int id_numerario_inicial, int troco[]);

int caixa[QT_VAL_DISTINTOS];

int main()
{
	int total; /* total a trocar */
        int resultado; /* resultado da operacao de troco */
        /* ler qtd. de notas e moeadas em caixa */
	lerInts(QT_VAL_DISTINTOS,caixa);
	printf("======= Estado inicial =======\n");
	printf("caixa (total = %d):\n", totalizarNumerario(caixa));
	exibirCabecalho();
	exibirNumerario(caixa);
        while (1) {
                scanf("%d", &total);
                if (total==0) break;
        	printf("======= Trocar %d =======\n", total);
                assert(totalizarNumerario(caixa) >= total);
                resultado = trocar(total);
		if (SEM_TROCO == resultado) {
			printf("*** sem troco ***\n");
		} else {
			/*exibirNumerario(caixa);*/
		}
        };
        return 0;
}

int lerInts(int qtd_ler, int vetor[])
{
	/* preenche o vetor com qtd_ler inteiros lidos de 
	   uma linha via stdin */
	char linha[80];  /* buffer de entrada */ 
	char delim[] = " \t"; /* delimtadores: branco e tab */
	char *lido = NULL;
	int qtd_lidos = 0;
	fgets(linha, sizeof(linha), stdin);
	lido = strtok(linha, delim);
	while( lido != NULL && qtd_lidos < qtd_ler) {
		vetor[qtd_lidos] = atoi(lido);
		qtd_lidos++;
		lido = strtok(NULL, delim);
	} 
	assert(qtd_ler==qtd_lidos);
	return qtd_lidos;
}

void exibirCabecalho()
{
	unsigned int i;
	int r, c; /* reais, centavos */
        printf("   ");
	for (i=0;i<QT_VAL_DISTINTOS;++i) {
		r = VAL_NUMERARIO[i] / 100;
		c = VAL_NUMERARIO[i] % 100;
		printf("R$ %d,%02d  ",r,c);
	}
	printf("\n");
}

void exibirNumerario(int numerario[])
{
	unsigned int i;
	printf("    ");
	for (i=0;i<QT_VAL_DISTINTOS;++i) {
		printf("%7d  ",numerario[i]);
	}
	printf("\n");
}

void zerarNumerario(int numerario[])
{
        unsigned int i;
        for (i=0;i<QT_VAL_DISTINTOS;++i) {
                numerario[i] = 0;
        }
}

void retirarNumerario(int caixa[], int troco[])
{
        unsigned int i;
        for (i=0;i<QT_VAL_DISTINTOS;++i) {
                caixa[i] -= troco[i];
        }
}

int totalizarNumerario(int numerario[])
{
        /* calcular valor total de notas e moedas */
        unsigned int i;
        int total = 0;
        for (i=0;i<QT_VAL_DISTINTOS;++i) {
                total += VAL_NUMERARIO[i] * numerario[i];
        }
        return total;
}

int trocar(const int total)
{
        int troco[QT_VAL_DISTINTOS];
        int resultado;
        zerarNumerario(troco);
        resultado = fazerTroco(total, 0, troco);
        if (SEM_TROCO == resultado) {
                return SEM_TROCO;
        } else {
                assert(resultado==total);
                exibirCabecalho(troco);
                exibirNumerario(troco);
                /* retirarNumerario(caixa, troco); */
                return total;
        }
}

int fazerTroco(const int total, const unsigned int id_num_inic, int troco[])
{
        unsigned int id_numerario;
        int qt_numerario, qt_num_maximo;
        int valor, resto, resultado;
        for (id_numerario=id_num_inic; id_numerario<QT_VAL_DISTINTOS; ++id_numerario) {
                valor = VAL_NUMERARIO[id_numerario];
                if (valor > total)
                        continue;
                qt_num_maximo = total / valor;
                if (qt_num_maximo > caixa[id_numerario]) {
                        qt_num_maximo = caixa[id_numerario];
                }
                resto = total - qt_num_maximo * valor;
                if (resto == 0) { /* encontramos o troco exato */
                        troco[id_numerario] = qt_num_maximo;
                        return total;
                }
                if (id_numerario==(QT_VAL_DISTINTOS-1)) {
                        /* já estamos no numerário de menor valor */
                        return SEM_TROCO;
                }
                /* fazer troco para o resto; reduzir qt_numerario se preciso */
                for (qt_numerario=qt_num_maximo; qt_numerario>0;--qt_numerario) {
                        resultado = fazerTroco(resto, id_numerario+1, troco);
                        if (resultado!=SEM_TROCO) {
                                troco[id_numerario] = qt_numerario;
                                return total;
                        }
                        /* se ainda não fechamos o troco, aumentar o resto */
                        resto += valor;
                }
                
        }
        return SEM_TROCO;

}
